package com.universe.arithmetic.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author：ghostbamboo
 * @Description： 二分查找法
 * @Theory： CONTENT
 * @Date： 10:22 2020/1/6
 */
public class BinarySearch {

    //统计执行次数
    public static int count = 0;

    /**
     * 二分查找法(递归实现)
     *
     * @param left  要查找的数组起始索引
     * @param right 要查找的数组终止索引
     * @param arr   要查找的数组
     * @param value 要查找的值
     * @return 返回下标
     */
    public static int binarySearch(int left, int right, int[] arr, int value) {
        count++;

        int mid = (left + right) / 2;
        if (left > right) {
            return -1;
        }
        //向左递归查找
        if (arr[mid] > value) {
            return binarySearch(left, mid, arr, value);
        } else if (arr[mid] < value) {        //向右递归查找
            return binarySearch(mid + 1, right, arr, value);
        } else {
            return mid;
        }
    }

    /**
     * 二分查找法(可以返回重复的值)
     */
    public static List<Integer> binarySearch2(int left, int right, int[] arr, int value) {
        int mid = (left + right) / 2;
        if (left > right) {
            return new ArrayList<>();
        }
        //向左递归查找
        if (arr[mid] > value) {
            return binarySearch2(left, mid, arr, value);
        } else if (arr[mid] < value) {        //向右递归查找
            return binarySearch2(mid + 1, right, arr, value);
        } else {
            /*
             * 思路分析
             * 1. 在找到mid 索引值，不要马上返回
             * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
             * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
             * 4. 将Arraylist返回
             */
            List<Integer> list = new ArrayList<>();
            list.add(mid);
            //向左扫描
            int index = mid - 1;
            while (arr[index] == arr[mid]) {
                list.add(index);
                index--;
            }
            //向右扫描
            index = mid + 1;
            while (arr[index] == arr[mid]) {
                list.add(index);
                index++;
            }
            return list;
        }
    }

    public static int binarySearchByNoRecursion(int[] arr, int value) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > value) {
                right = mid;
            } else if (arr[mid] < value) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        //int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 11, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int value = 20;
        int res = binarySearch(0, arr.length - 1, arr, value);
        //int res = binarySearchByNoRecursion(arr, value);
        if (res != -1) {
            System.out.printf("找到 %d 对应的下标为 %d ", value, res);
        } else {
            System.out.println(value + " 没有找到");
        }
        System.out.println("\n执行次数为: " + count);

        //重复数据查找
        //List<Integer> res = binarySearch2(0, arr.length - 1, arr, value);
        //if (res != null && res.size() > 0) {
        //    System.out.print("\n找到 " + value + " 对应的下标为: ");
        //    for (Integer re : res) {
        //        System.out.print(re + " ");
        //    }
        //} else {
        //    System.out.println(value + " 没有找到");
        //}
    }
}
